Data storage systems are arrangements of hardware and software that include one or more storage processors coupled to arrays of non-volatile storage devices, such as magnetic disk drives, electronic flash drives, and/or optical drives, for example. The storage processors service storage requests, arriving from host machines (“hosts”), which specify files or other data elements to be written, read, created, or deleted, for example. Software running on the storage processors manages incoming storage requests and performs various data processing tasks to organize and secure the data elements stored on the non-volatile storage devices.
Data storage systems commonly employ file systems for serving files and directories to hosts and/or for internal data management. A file system may represent a file using an inode (index node), which has a unique inode number within the file system and includes pointers to data blocks that store file data. The data blocks are units of storage, which may be 8 KB in size, for example; however, different file systems may use different data block sizes and some file systems may use multiple data block sizes. The inode may include pointers to indirect blocks (IDBs), i.e., blocks which themselves store arrays of pointers. The pointers may point to data blocks or to other IDBs. IDBs may be arranged in trees, with a pointer in one IDB pointing to another IDB, ultimately terminating in a leaf IDB that points to data blocks. The use of IDB trees allows files to grow to very large sizes.
Many file systems support block sharing, i.e., arrangements of metadata that allow multiple objects to point to some or all of the same data blocks. Block sharing avoids having to create redundant copies of the same blocks when those blocks are shared among multiple files. In some examples, files that share blocks in a data storage system are snapshots that provide point-in-time versions of files, and/or clones that provide multiple versions of the same file, e.g., for deployment of a golden image.
A common task performed by file systems that support block sharing is to keep track of numbers of objects that reference data blocks. For example, when a file system performs an operation to delete a data block referenced by an object, the file system must have some way of determining whether any other object is also referencing the data block, so that the file system avoids deleting data that another object relies upon.
Many approaches have been used to track block sharing. One approach stores a field in each block pointer (i.e., in each pointer in an inode or IDB) that indicates whether the block pointer is an owner or a non-owner of the data block. If a file system attempts to delete a non-owner block pointer (e.g., as part of deleting a file or a portion of a file), the file system may delete the block pointer but leave the data block it points to in place. However, if the file system attempts to delete an owner block pointer, the file system first checks for any non-owners. If a non-owner is found, the file system may delete the owner block pointer and transfer its ownership to the non-owner block pointer, making it the owner and, again, leaving the pointed-to data block in place. If no non-owner is found, the file system may delete the owner block pointer and free the data block, e.g., by marking it as available to be allocated elsewhere.
Another approach used to track block sharing is to employ integer reference counts. With this approach, a file system stores a reference count for each data block. The reference count for a data block counts the number of block pointers that point to that data block. When a new block pointer is made to point to a data block, the reference count of that data block is incremented by one. When a block pointer pointing to the data block is deleted or pointed elsewhere, the reference count of the data block is decremented by one. If the reference count falls to zero, there are no remaining references and the data block may be freed.
Yet another approach used to track block sharing employs weighted reference counts. Here, each block pointer separately records a number of shares it has in a data block to which it points. Whenever a data block is shared from a new pointer, the number of shares is distributed between the pointers.